// 给定 () [] {} 三组括号,判断是否为有效字符串
// 括号能够正确闭合且顺序不能错,如: ({[]}) ()[]{}
// 这道题目可以适用栈的特性很轻松地解决(后入先出)
// 但是要注意题目中特殊用例的判断不能出错,如: "[)" "" "]"这些

typedef char STDataType ;

typedef struct Stack
{

    STDataType* arr ;

    int top ; // 指向栈顶的位置

    int capacity ; // 栈的容量

} ST ;

// 栈的初始化

void StackInit (ST* ps)
{

    ps -> arr = NULL ;

    ps -> top = ps -> capacity = 0 ;

}

// 栈的销毁

void StackDestory (ST* ps)
{

    if (ps -> arr)
    {

        free (ps -> arr) ;

    }
    
        ps -> arr = NULL ;

        ps -> top = ps -> capacity = 0 ;

}

// 栈是否为空

bool StackEmpty (ST* ps)
{

    assert (ps) ;

    return ps -> top == 0 ;

}

// 入栈---从栈顶

void StackPush (ST* ps , STDataType x)
{

    assert (ps) ;

    if (ps -> top == ps -> capacity)

    {

        // 增容

        int newcapacity = ps -> capacity == 0 ? 4 : 2 * ps -> capacity ;

        STDataType* tmp = (STDataType*) realloc (ps -> arr , newcapacity * sizeof (STDataType)) ;

        if (tmp == NULL)
        {

            perror ("realloc fail!") ;

            exit (1) ;

        }

        ps -> arr = tmp ;

        ps -> capacity = newcapacity ;

    }

    ps -> arr [ps -> top++] = x ;

}

// 出栈---从栈顶

void StackPop (ST* ps)
{

    assert (!StackEmpty (ps)) ;

    --ps -> top ;

}

// 取栈顶元素

STDataType StackTop (ST* ps)
{

    assert (!StackEmpty (ps)) ;

    return ps -> arr [ps -> top - 1] ;

}

// 获取栈中有效元素个数

int StackSize (ST* ps)
{

    return ps -> top ;
    
}

bool isValid(char* s) 
{

    ST st ;

    StackInit (&st) ;

    char* pi = s ;

    while (*pi != '\0')
    {

        if (*pi == '(' || *pi == '[' || *pi== '{')
        {

            StackPush (&st , *pi) ;

        }

        if (*pi == ')' || *pi == ']' || *pi == '}')
        {

            if (StackEmpty (&st))
            {

                StackDestory (&st) ;

                return false ;

            }

            STDataType top = StackTop (&st) ;

            if (*pi == ')' && top != '(' || *pi == ']' && top != '[' || *pi == '}' && top != '{')
            {

                StackDestory (&st) ;

                return false ;

            }

            StackPop (&st) ;

        }

        pi++ ;

    }

    bool ret = StackEmpty (&st) ? true : false ;

    StackDestory (&st) ;

    return ret ;
    
}